// 题目：https://www.nowcoder.com/practice/a9d0ecbacef9410ca97463e4a5c83be7?tpId=13&tqId=1374963&ru=%2Fpractice%2F7fe2212963db4790b57431d9ed259701&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3Fpage%3D1%26tpId%3D13%26type%3D13
// 思路1：1.递归实现；
// 思路2：1.递归栈实现；交换左右两边即可；

#include <algorithm>
#include <climits>
#include <queue>
#include <vector>
#include <stack> 
#include <limits>

using namespace std;
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};


class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pRoot TreeNode类 
     * @return TreeNode类
     */
    TreeNode* Mirror(TreeNode* pRoot) {
        // write code here
        if (pRoot == nullptr) return nullptr;

        // auto tmp_node = pRoot->left;
        // pRoot->left = pRoot->right;
        // pRoot->right = tmp_node;
        // Mirror(pRoot->left);
        // Mirror(pRoot->right);

        TreeNode* tmp = pRoot->right;
        pRoot->right = Mirror(pRoot->left);
        pRoot->left = Mirror(tmp);

        return pRoot;
    }
};

#include <stack>
class Solution {
public:
    TreeNode* Mirror(TreeNode* root) {
        if(!root) 
            return root; //判断边界条件
        stack<TreeNode*> stack;//定义递归栈
        TreeNode* temp;//定义一个缓冲指针
        stack.push(root);//压入头节点
        while (!stack.empty())
        {
            TreeNode* node = stack.top();
            //头结点出栈
            stack.pop();
            //将左右节点入栈
            if (node->left) 
                stack.push(node->left);
            if (node->right) 
                stack.push(node->right);
            //交换左右节点
            temp = node->left;
            node->left = node->right;
            node->right = temp;
        }
        return root;
    }
};